/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-07-26
 * Time: 9:18
 */

  class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }


public class Test {

      //排序链表
    public ListNode sortList(ListNode head) {
        return mergeSort(head,null);
    }

    private ListNode mergeSort(ListNode head,ListNode tail) {
        if(head == null) {
            return head;
        }
        if(head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid  = slow;
        ListNode list1 = mergeSort(head,mid);
        ListNode list2 = mergeSort(mid,tail);
        ListNode sorted = merge(list1,list2);
        return sorted;
    }

    private ListNode merge(ListNode list1,ListNode list2) {
        ListNode phead = new ListNode(-1);
        ListNode cur = phead;
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                cur.next = list1;
                cur = cur.next;
                list1 = list1.next;
            }else {
                cur.next = list2;
                cur = cur.next;
                list2 = list2.next;
            }
        }
        if(list1 != null) {
            cur.next = list1;
        }
        if(list2 != null) {
            cur.next = list2;
        }

        return phead.next;
    }

    public ListNode createNode() {
        ListNode A = new ListNode(4);
        ListNode B = new ListNode(2);
        ListNode C = new ListNode(1);
        ListNode D = new ListNode(3);
        A.next = B;
        B.next = C;
        C.next = D;
        return A;
    }

    public ListNode sortList1(ListNode head) {
        int size = 0;
        ListNode tmp = head;
        while(tmp != null) {
            size++;
            tmp = tmp.next;
        }
        ListNode phead = new ListNode(-1,head);

        for(int length = 1; length < size; length *= 2) {
            ListNode cur = phead.next;
            ListNode prev = phead;
            while(cur != null) {
                ListNode list1 = cur;
                for(int i = 1; i < length && cur.next != null; i++) {
                    cur = cur.next;
                }
                ListNode curNext1 = cur.next;
                cur.next = null;
                cur = curNext1;
                ListNode list2 = cur;
                for(int i = 1; i < length && cur != null && cur.next != null; i++) {
                    cur = cur.next;
                }
                ListNode curNext2 = null;
                if(cur != null) {
                    curNext2 = cur.next;
                    cur.next = null;
                }
                ListNode sorted = merge(list1,list2);
                prev.next = sorted;
                while(prev.next != null) {
                    prev = prev.next;
                }
                cur = curNext2;
            }
        }
        return phead.next;
    }

    private ListNode merge1(ListNode list1,ListNode list2) {
        ListNode phead = new ListNode(-1);
        ListNode cur = phead;
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                cur.next = list1;
                cur = cur.next;
                list1 = list1.next;
            }else {
                cur.next = list2;
                cur = cur.next;
                list2 = list2.next;
            }
        }
        if(list1 != null) {
            cur.next = list1;
        }
        if(list2 != null) {
            cur.next = list2;
        }

        return phead.next;
    }
}
